"""
三种颜色染色，不能有连续三个同色，问方案总数
令Fi为i格染色方案，则在F[i-1]的基础上任意两种颜色均可
在F[i-2]的基础上同样任意两种颜色均可
且是完备的
"""
MOD = 1000000000 + 7
F = [0 for i in range(100000 + 1)]
F[0] = 1
F[1] = 3
F[2] = 9
for i in range(3, 100000 + 1):
    F[i] = (F[i - 1] + F[i - 2]) % MOD * 2 % MOD
    
nofkase = int(input())
for kase in range(nofkase):
    print(int(F[int(input())]))